import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	/**
	 * @param args
	 */
	
	private static final int MAX_VALUE = 1<<28; 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine());
		while (testCases--!=0) {
			String st = br.readLine();
			StringTokenizer sToken = new StringTokenizer(st);
			int n = Integer.parseInt(sToken.nextToken());
			int t = Integer.parseInt(sToken.nextToken());
			
			int risk[][][] = new int[n][n][n];
			int time[][][] = new int[n][n][n];
			for (int i = 0; i < n; i++) {
				st = br.readLine();
				sToken = new StringTokenizer(st);
				int j = 0;
				while (sToken.hasMoreTokens()) {
					time[i][j++][0] = Integer.parseInt(sToken.nextToken());
				}
			}
			for (int i = 0; i < n; i++) {
				st = br.readLine();
				sToken = new StringTokenizer(st);
				int j = 0;
				while (sToken.hasMoreTokens()) {
					risk[i][j++][0] = Integer.parseInt(sToken.nextToken());
				}
			}
		
			for(int k = 1; k < n; k++) {
				for(int i = 0; i < n; i++) {
					for(int j = 0; j < n; j++) {
						if(risk[i][j][k - 1] == risk[i][k][k - 1] + risk[k][j][k - 1]) {
							if(time[i][j][k - 1] > time[i][k][k - 1] + time[k][i][k - 1]) {
								time[i][j][k] = time[i][k][k -1] + time[k][j][k - 1];
							}
						} else if(risk[i][j][k - 1] > risk[i][k][k - 1] + risk[k][j][k - 1]) {
							risk[i][j][k] = risk[i][k][k - 1] + risk[k][j][k - 1];
							time[i][j][k] = time[i][k][k - 1] + time[k][j][k - 1];
						} else {
							if(time[i][j][k - 1] > t && time[i][k][k - 1] + time[k][i][k - 1] <= t) {
								risk[i][j][k] = risk[i][k][k - 1] + risk[k][j][k - 1];
								time[i][j][k] = time[i][k][k - 1] + time[k][j][k - 1];
							}
						}
					}
				}
			}
			
			if(time[0][n - 1][n - 1] > t) {
				System.out.println(-1);
			} else {
				System.out.println(risk[0][n - 1][n - 1] + " " + time[0][n - 1][n - 1]);
			}
		}
	}

}

